Reducing Tile Complexity for Self-Assembly Through Temperature Programming

摘要

We consider the tile self-assembly model and how tile complexity can beeliminated by permitting the temperature of the self-assembly system to beadjusted throughout the assembly process. To do this, we propose noveltechniques for designing tile sets that permit an arbitrary length $m$ binarynumber to be encoded into a sequence of $O(m)$ temperature changes such thatthe tile set uniquely assembles a supertile that precisely encodes thecorresponding binary number. As an application, we show how this provides ageneral tile set of size O(1) that is capable of uniquely assemblingessentially any $n\times n$ square, where the assembled square is determined bya temperature sequence of length $O(\log n)$ that encodes a binary descriptionof $n$. This yields an important decrease in tile complexity from the required$\Omega(\frac{\log n}{\log\log n})$ for almost all $n$ when the temperature ofthe system is fixed. We further show that for almost all $n$, no tile systemcan simultaneously achieve both $o(\log n)$ temperature complexity and$o(\frac{\log n}{\log\log n})$ tile complexity, showing that both versions ofan optimal square building scheme have been discovered. This work suggests thattemperature change can constitute a natural, dynamic method for providing inputto self-assembly systems that is potentially superior to the current techniqueof designing large tile sets with specific inputs hardwired into the tileset.